package com.test.daily.leetcode.y2022.m07.day0702.v02;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/2 下午 01:35
 * @version: 1.0
 */
public class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations){
        int N = stations.length;
        long[] dp = new long[N+1];
        dp[0] = startFuel;
        for(int i = 0; i < N; i++){
            for(int j = i; j >= 0; j--){
                if(dp[j] >= stations[i][0]){
                    dp[j+1] = Math.max(dp[j+1], dp[j] + stations[i][1]);
                }
            }
        }
        for(int i = 0; i <= N; i++){
            if(dp[i] >= target){
                return i;
            }
        }
        return -1;
    }
}
